/*
 * @lc app=leetcode.cn id=839 lang=java
 *
 * [839] 相似字符串组
 */

// @lc code=start
class Solution {
    //这题也不用是hard吧。
    public int numSimilarGroups(String[] strs) {
        int len = strs.length;
        UnionFind uf = new UnionFind(len);
        for (int i = 0; i < len; i++) {
            for (int j = i+1; j < len; j++) {
                if(check(strs[i], strs[j])){//如果两个字符串可相似，并起来
                    uf.union(i, j);
                }
            }
        }
        return uf.getCount();
    }

    /**
     * 用来检查两个字符串是否是相似的。
     * @param a
     * @param b
     * @return
     */
    public boolean check(String a ,String b){
        int len = a.length();
        int cnt = 0;
        for(int i = 0 ;i<len ;i++){
            if(a.charAt(i)!=b.charAt(i)) cnt++;
        }
        return cnt<=2;//是0或者2
    }
    
    class UnionFind {
        int[] parent;
        int[] size;
        int n;
        int count;//记录联通分量数目
        public UnionFind(int n) {
            this.n = n;
            this.count = n;
            this.parent = new int[n];
            this.size = new int[n];
            Arrays.fill(size, 1);
            for (int i = 0; i < n; ++i) 
                parent[i] = i;
        }

        public int find(int x) {
            return parent[x] == x ? x : (parent[x] = find(parent[x]));
        }

        public boolean union(int x, int y) {
            x = find(x);
            y = find(y);
            if (x == y) 
                return false;
            if (size[x] < size[y]) {
                int temp = x;
                x = y;
                y = temp;
            }
            count--;
            parent[y] = x;
            size[x] += size[y];
            return true;
        }

        public int getCount(){
            return this.count;
        }
    }
}
// @lc code=end

